// https://leetcode.cn/problems/longest-increasing-path-in-a-matrix/

// 题干：给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度。
//       对于每个单元格，你可以往上，下，左，右四个方向移动。
//       你 不能 在 对角线 方向上移动或移动到 边界外（即不允许环绕）。

// 示例：输入：matrix = [[9,9,4],[6,6,8],[2,1,1]]
//      输出：4

// 碎语：记忆化搜索，递归等的合体题，较为综合

#include <bits/stdc++.h>
using namespace std;

class Solution
{
    int m, n;
    int memo[201][201];
    int dx[4] = {-1,1,0,0};
    int dy[4] = {0,0,-1,1};

public:
    int longestIncreasingPath(vector<vector<int>>& matrix)
    {
        int ret = 0;
        m = matrix.size(), n = matrix[0].size();
        memset(memo, 0, sizeof(memo));

        for (int i = 0 ; i < m ; i++){
            for (int j = 0 ; j < n ; j++){
                ret = max(ret, dfs(matrix, i, j));
            }
        }

        return ret;
    }

    int dfs(vector<vector<int>>& matrix, int i, int j)
    {
        if (memo[i][j]) return memo[i][j];

        int ret = 1;

        for (int k = 0 ; k < 4 ; k++){
            int x = i + dx[k], y = j + dy[k];
            if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j]){
                ret = max(ret, dfs(matrix, x, y) + 1);
            }
        }
        memo[i][j] = ret;

        return ret;
    }
};

int main()
{
    Solution sol;
    vector<vector<int>> matrix = {{9,9,4},{6,6,8},{2,1,1}};

    cout << sol.longestIncreasingPath(matrix) << endl;

    return 0;
}
